\section{Introduction}
The purpose of this project was to implement a serializable transactional read and write data store using the Google App Engine API.
Thus there are two aspects to this project: a comparative implementation of two concurrency control strategies: Two Phase Locking and Optimistic Concurrency Control (OCC), and the usage of Google App Engine \cite{gae} especially its key-value type DataStore API. The key-value datastores are the "new age" data stores with the upside of being more scalable that a traditional database by compromising on the some of the guarantees of the traditional relational database. The other notable key-value datastores are Dynamo \cite{dynamo} and PNUTS \cite {pnuts}

\subsection {Concurrency Control}
Database Concurrency control is a mechanism that allows operations from different transactions to be interleaved but still appear from the user point of view to have executed in a serial fashion. The two main strategies employed for concurrency control are Optimistic Concurrency Control \cite{kungocc} and Locking. The locking protocols require transactions to acquire locks on data items they wish to operate on before proceeding with execution. This prevents conflicting operations (operation on the same data items with at-least one of them being write) amongst two transaction from accessing the same data item. In contrast Optimistic Concurrency Control protocol relies on the assumption that most transactions do not have conflicting operations. Thus transactions in OCC proceed concurrently and are validated for serializability only when they commit. In case a non serializable transaction is detected, it is aborted or retried. 

Amongst the locking protocols two phase locking protocols is the one utilized in most commercial database systems. We have implemented the Strong Strict Two Phase Locking (SS2PL) variation of the two phase locking protocol. This protocol mandates that transactions release any locks that they hold only after completion i.e. after a commit or an abort. 
OCC has two variations - Serial Validation and Parallel Validation, which differ in terms of whether two or more transactions can be validated simultaneously. While serial validation disallows two transactions to be validating simultaneously, parallel validation permits this with an extra restriction on conflicting operations between transactions. Our implementation is based on parallel validation protocol of OCC. Section 2 further details the implementation of these two strategies, including the data structures used for locking and data storage.

\subsection{Google App Engine}
GAP is a Platform as a Service offering from Google, which allows users to run web applications using Google's infrastructure in a sandbox environment. The primary selling point of the App engine is the inbuilt scalability. The scalability is provided through the platform which is built on tested scalable technologies such as BigTable \cite{bigtable} and Google File System \cite{gfs}. In order to ensure application scalability the platform does enforce some restrictions which we discuss in the next section. The platforms consists of a python runtime and variety of Service APIs such as the Datastore API for persistent storage, Memcahce API for caching etc. The Datastore is a \textbf{distributed} data storage service that supports querying and transactions. It allows the application to store data without the application having access to the any disk directly. 

In Section 2 we discuss the implementation details of the two strategies as well as the details of Google App engine APIs and features utilized for the implementation. Section 3 describes the details on performance testing of the two implementations. 

